#include <bits/stdc++.h>
using namespace std;
const int MOD = 2017;
typedef long long LL;
typedef vector<int> vi;
struct Mat {
  int r, c;
  vector<vi> f;
  Mat(int _r, int _c) : r(_r), c(_c), f(r + 1, vi(c + 1)) {}
  Mat operator*(const Mat& b) const {
    Mat m(r, b.c);
    for (int i = 1; i <= m.r; ++i)
      for (int j = 1; j <= m.c; ++j)
        for (int k = 1; k <= m.c; ++k) {
          m.f[i][j] = (m.f[i][j] + f[i][k] * b.f[k][j] % MOD) % MOD;
        }
    return m;
  }
  Mat operator^(LL x) const {
    assert(r == c);
    Mat m = *this, p = *this;
    for (--x; x; x >>= 1, p = p * p)
      if (x & 1) m = m * p;
    return m;
  }
};
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, m, t;
  cin >> n >> m;
  ++n;
  Mat G(n, n);
  for (int u, v, i = 1; i <= m; ++i) cin >> u >> v, G.f[u][v] = G.f[v][u] = 1;
  for (int i = 1; i <= n; ++i) {
    G.f[i][i] = 1;
  }
  // 加上一条向“自爆”状态转移的边
  for (int i = 1; i <= n - 1; ++i) {
    G.f[i][n] = 1;
  }
  cin >> t;
  G = (G ^ t);
  int ans = 0;
  for (int i = 1; i <= n; ++i) ans = (ans + G.f[1][i]) % MOD;
  cout << ans << endl;
}
